/**
 * Hierholzer 算法求解欧拉路径
 * 1. 根据每个节点的度数，确定欧拉路径/欧拉回路的起点。
 * 2. 从起点开始执行遍历所有边的 DFS 算法，记录后序遍历结果。
 * 3. 最后，将后序遍历结果反转，即可得到欧拉路径/欧拉回路。对于无向图，由于边没有方向的区别，所以即便不反转，结果也是对的。
 */
function solveOneStroke(graph) {
  // 根据度数确定起点（题目保证必然存在欧拉路径）
  let start = 0;
  for (let node in graph) {
    if (graph[node].length % 2 === 1) {
      start = +node;
      break;
    }
  }

  // 从起点开始执行 DFS 算法，记录后序遍历结果
  let postOrder = [];
  traverse(graph, start, postOrder);
  // 反转后序遍历结果，即可得到欧拉路径
  console.log(postOrder.reverse());
}

function traverse(graph, s, postOrder) {
  while (graph[s].length > 0) {
    // 无向图，删除两条边
    let neighbor = graph[s].pop();
    graph[neighbor].splice(graph[neighbor].indexOf(s), 1);

    traverse(graph, neighbor, postOrder);
  }
  // 后序位置记录节点
  postOrder.push(s);
}

// test
// 图的邻接表表示
const graph = [
  [1, 4],
  [0, 3, 4, 5],
  [5],
  [1, 5],
  [0, 1],
  [1, 2, 3]
];
solveOneStroke(graph);